package cn.hycat.leetcode.middle;

import java.util.*;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
/*128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
    示例 1：
    输入：nums = [100,4,200,1,3,2]
    输出：4
    解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

    示例 2：
    输入：nums = [0,3,7,2,5,8,4,6,0,1]
    输出：9*/
public class L128最长连续序列 {
    public static int longestConsecutive(int[] nums) {
        if(nums.length < 2) return nums.length;

        HashSet<Integer> set = new HashSet();
        for(int i = 0; i < nums.length; i++)
            set.add(nums[i]);
        ArrayList<Integer> list = new ArrayList(set);
        Collections.sort(list);

        int[] dp = new int[set.size()];
        dp[0] = 1;
        int ans = 1;
        for(int i = 1; i < list.size(); i++) {
            dp[i] = list.get(i) - list.get(i-1) == 1 ? 1 + dp[i-1] : 1;
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {100,4,200,1,3,2};
        System.out.println(longestConsecutive(nums));
    }

    public static void print(List list) {
        for(int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}
